package leetcode.cn;

import java.util.Arrays;

/**
 * @version 1.8
 * @Author Djx_hmbb
 * @Date 2023/11/15 20:56
 * @注释:1658.将x减到 0 的最小操作数
 */
public class MinOperations {
    /*给你一个整数数组 nums 和一个整数 x 。每一次操作时，你应当移除数组 nums 最左边或最右边的元素，然后从 x 中减去该元素的值。请注意，需要 修改 数组以供接下来的操作使用。
如果可以将 x 恰好 减到 0 ，返回 最小操作数 ；否则，返回 -1 。

示例 1：
输入：nums = [1,1,4,2,3], x = 5
输出：2
解释：最佳解决方案是移除后两个元素，将 x 减到 0 。

示例 2：
输入：nums = [5,6,7,8,9], x = 4
输出：-1

示例 3：
输入：nums = [3,2,20,1,1,3], x = 10
输出：5
解释：最佳解决方案是移除后三个元素和前两个元素（总共 5 次操作），将 x 减到 0 。*/


    //错误理解和方法xxx【按照原数组进行计算，不能排序】
    public static int minOperations0(int[] nums, int x) {
        //暴力枚举：
        //先排序xxxxxxx
        Arrays.sort(nums);
        int n = nums.length, right = n - 1, len = 0;
        while (right >= 0) {
            //从右边开始判断
            //<=x，len++;x-[right--];
            if (nums[right] <= x) {
                len++;
                x -= nums[right--];
            } else right--;
            //判断x是否为0 ==0，return len；
            if (x == 0) return len;
        }
        return -1;
    }

    //老师的解法：
    public static int minOperations(int[] nums, int x) {
        //1. 计算出整个数组sum的值和target（代表窗口里面的和sum-x）的值
        int sum = 0;
        for (int i : nums) sum += i;
        int target = sum - x;
        //细节：
        //如果target<0（即x>sum），则直接返回-1
        if(target<0) return -1;
        //2. 进窗口
        int left = 0, right = 0, tmp = 0, len = -1;
        //这里长度len设为-1，有两个好处：
        // 1. 题目要求没有符合条件的就返回-1。
        // 2.最后可以判断，如果len是-1，则直接返回-1，否则返回num.length。
        while (right < nums.length) {
            tmp += nums[right];
            //3. 判断窗口里面的值
            while (tmp > target) {
                //大于target，[left++]
                //4. 出窗口
                tmp -= nums[left++];
            }
            if (tmp == target) {
                // 等于target，计算窗口长度
                //5. 更新长度
                len = Math.max(len, right - left+1);
            }
            // 小于target，right++
            //6. 进窗口
            right++;
        }
        if(len == -1) return len;
        return nums.length-len;
    }

    public static void main(String[] args) {
        int[] nums = {5,6,7,8,9};
        int x = 4;
        int i = minOperations(nums, x);
        System.out.println(i);
    }
}
